package leecode

func largestRectangleAreaLCR(heights []int) (result int) {
	heights = append([]int{0}, heights...)
	heights = append(heights, 0)
	stack := make([]int, 0)
	stack = append(stack, 0)
	for i := 1; i < len(heights); i++ {
		topIndex := stack[len(stack)-1]
		for len(stack) != 0 && heights[i] < heights[topIndex] {
			stack = stack[:len(stack)-1]
			h := heights[topIndex]
			w := i - stack[len(stack)-1] - 1
			result = max(result, h*w)
			topIndex = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	return
}
